package com.cn.algorithm.two.graph;


import com.cn.algorithm.two.union.GenericUnionFind;

import java.util.*;
import java.util.Map.Entry;

public class ListGraph<V, E> extends Graph<V, E> {


    public ListGraph(WeightManager<E> weightManager) {
        super(weightManager);
    }

    //顶点集合
    Map<V, Vertex<V, E>> vertices = new HashMap<>();
    //边集合
    Set<Edge<V, E>> edges = new HashSet<>();

    @Override
    public int edgeSize() {
        return edges.size();
    }

    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, null);
    }

    @Override
    public void addEdge(V from, V to, E weight) {
        Vertex<V, E> vertexFrom = vertices.get(from);
        if (vertexFrom == null) {
            vertexFrom = new Vertex<>(from);
            vertices.put(from, vertexFrom);
        }
        Vertex<V, E> vertexTo = vertices.get(to);
        if (vertexTo == null) {
            vertexTo = new Vertex<>(to);
            vertices.put(to, vertexTo);
        }
        Edge<V, E> edge = new Edge<>(vertexFrom, vertexTo);
        edges.add(edge);
        edge.to.in.add(edge);
        edge.from.out.add(edge);
    }


    @Override
    public void removeEdge(V from, V to) {
        Vertex<V, E> vertexFrom = vertices.get(from);
        if (vertexFrom == null) {
            return;
        }
        Vertex<V, E> vertexTo = vertices.get(to);
        if (vertexTo == null) {
            return;
        }
        Edge<V, E> edge = new Edge<>(vertexFrom, vertexTo);
        edge.from.out.remove(edge);
        edge.to.in.remove(edge);
        edges.remove(edge);
    }

    @Override
    public int vertexSize() {
        return vertices.size();
    }

    @Override
    public void addVertex(V value) {
        if (vertices.containsKey(value)) {
            return;
        }
        vertices.put(value, new Vertex<>(value));

    }

    @Override
    public void removeVertex(V value) {
        Vertex<V, E> vertex = vertices.remove(value);
        if (vertex == null) {
            return;
        }
        Iterator<Edge<V, E>> iteratorIn = vertex.in.iterator();
        while (iteratorIn.hasNext()) {
            Edge<V, E> edge = iteratorIn.next();
            edge.from.out.remove(edge);
            iteratorIn.remove();
            edges.remove(edge);
        }
        Iterator<Edge<V, E>> iteratorOut = vertex.out.iterator();
        while (iteratorOut.hasNext()) {
            Edge<V, E> edge = iteratorOut.next();
            edge.to.in.remove(edge);
            iteratorOut.remove();
            edges.remove(edge);
        }
    }

    @Override
    public void breadthFirstSearch(V v) {
        Vertex<V, E> vertex = vertices.get(v);
        if (vertex == null) {
            return;
        }
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        Set<V> hasSelected = new HashSet<>();
        queue.offer(vertex);
        hasSelected.add(v);
        while (!queue.isEmpty()) {
            Vertex<V, E> poll = queue.poll();
            for (Edge<V, E> edge : poll.out) {
                if (hasSelected.contains(edge.to.value)) {
                    continue;
                }
                queue.add(edge.to);
                hasSelected.add(edge.to.value);
            }
        }
    }

    @Override
    public void depthFirstSearch(V begin) {
        Vertex<V, E> vertex = vertices.get(begin);
        if (vertex == null) {
            return;
        }
        Set<V> hasSelected = new HashSet<>();
        Stack<Vertex<V, E>> stack = new Stack<>();
        stack.push(vertex);
        while (!stack.isEmpty()) {
            Vertex<V, E> pop = stack.pop();
            for (Edge<V, E> edge : pop.out) {
                if (hasSelected.contains(edge.to.value)) {
                    continue;
                }
                stack.push(edge.from);
                stack.push(edge.to);
                hasSelected.add(edge.to.value);
                System.out.println(edge.to.value);
                break;
            }

        }

    }

    @Override
    public List<V> topologicalSort() {
        if (vertices.size() == 0) {
            return null;
        }
        List<V> list = new ArrayList<>();
        Map<V, Integer> count = new HashMap<>();
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        vertices.values().forEach((Vertex<V, E> v) -> {
            int size = v.in.size();
            if (size == 0) {
                queue.offer(v);
            } else {
                count.put(v.value, size);
            }
            while (!queue.isEmpty()) {
                Vertex<V, E> vertex = queue.poll();
                list.add(vertex.value);
                for (Edge<V, E> edge : vertex.out) {
                    int currentSize = edge.to.in.size() - 1;
                    if (currentSize == 0) {
                        queue.offer(edge.to);
                    } else {
                        count.put(edge.to.value, currentSize);
                    }
                }
            }
        });
        return list;
    }

    @Override
    public Set<EdgeInfo<V, E>> minimumSpanningTree() {
        return Math.random() > 0.5 ? prim() : kruskal();
    }

    @Override
    public Map<V, PathInfo<V, E>> shortestPath(V begin) {
        return dijkstra(begin);
    }

    private Map<V, PathInfo<V, E>> dijkstra(V begin) {
        Vertex<V, E> vertex = vertices.get(begin);
        if (vertex == null) {
            return null;
        }
        Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
        Map<V, PathInfo<V, E>> selectedPath = new HashMap<>();
        for (Edge<V, E> edge : vertex.out) {
            PathInfo<V, E> pathInfo = new PathInfo<V, E>();
            pathInfo.weight = edge.weight;
            pathInfo.edgeInfos.add(edge.info());
            paths.put(edge.to, pathInfo);
        }
        while (!paths.isEmpty()) {
            Entry<Vertex<V, E>, PathInfo<V, E>> minPath = getMinPath(paths);
            Vertex<V, E> minVertex = minPath.getKey();
            PathInfo<V, E> minPathInfo = minPath.getValue();
            selectedPath.put(minVertex.value, minPathInfo);
            paths.remove(minVertex);
            for (Edge<V, E> edge : minVertex.out) {
                if (selectedPath.containsKey(edge.to.value)) {
                    continue;
                }
                relaxForDijkstra(edge, minPathInfo, paths);
            }

        }
        return selectedPath;
    }

    private void relaxForDijkstra(Edge<V, E> edge, PathInfo<V, E> minPathInfo,  Map<Vertex<V, E>, PathInfo<V, E>> paths) {
        E newWeight = weightManager.add(minPathInfo.weight, edge.weight);
        PathInfo<V, E> oldPath = paths.get(edge.to);
        if (oldPath != null) {
            if (weightManager.compare(newWeight, oldPath.weight) > 0) {
                return;
            } else {
                oldPath.edgeInfos.clear();
            }
        } else {
            oldPath = new PathInfo<>();
            paths.put(edge.to, oldPath);
        }
        oldPath.weight= newWeight;
        oldPath.getEdgeInfos().addAll(minPathInfo.getEdgeInfos());
        oldPath.getEdgeInfos().add(edge.info());
    }


    private Entry<Vertex<V, E>, PathInfo<V, E>> getMinPath(Map<Vertex<V, E>, PathInfo<V, E>> paths) {
        Iterator<Entry<Vertex<V, E>, PathInfo<V, E>>> iterator = paths.entrySet().iterator();
        Entry<Vertex<V, E>, PathInfo<V, E>> min = iterator.next();
        while (iterator.hasNext()) {
            Entry<Vertex<V, E>, PathInfo<V, E>> entry = iterator.next();
            if (weightManager.compare(min.getValue().weight, entry.getValue().weight) < 0) {
                min = entry;
            }
        }
        return min;
    }





    Comparator<Edge<V, E>> edgeComparator = new Comparator<Edge<V, E>>() {
        @Override
        public int compare(Edge<V, E> e1, Edge<V, E> e2) {
            return weightManager.compare(e1.weight, e2.weight);
        }
    };
    /*
    * prim算法(切割定律)
    *
    */
    private Set<EdgeInfo<V, E>> prim() {
        Iterator<Vertex<V, E>> iterator = vertices.values().iterator();
        if (!iterator.hasNext()) {
            return null;
        }
        Vertex<V, E> vertex = iterator.next();
        Set<EdgeInfo<V, E>> infos = new HashSet<>();
        Set<Vertex<V, E>> hasSelected = new HashSet<>();
        MinHeap<Edge<V, E>> minHeap = new MinHeap<>(vertex.out, edgeComparator);
        int vertexSize = vertices.size();
        while (!minHeap.isEmpty() && hasSelected.size() < vertexSize) {
            Edge<V, E> edge = minHeap.remove();
            if (hasSelected.contains(edge.to)) {
                continue;
            }
            infos.add(edge.info());
            hasSelected.add(edge.to);
            //将第二个顶点的所有出度边加入最小堆，重新排序，选择最小一条边
            minHeap.addAll(edge.to.out);
        }
        return infos;
    }

    private Set<EdgeInfo<V, E>> kruskal() {
        if (edges.size() == 0) {
            return null;
        }
        GenericUnionFind<Vertex<V, E>> uf = new GenericUnionFind<>();
        vertices.values().forEach(veVertex -> {
            uf.put(veVertex);
        });
        Set<EdgeInfo<V, E>> infos = new HashSet<>();
        MinHeap<Edge<V, E>> minHeap = new MinHeap<>(edges, edgeComparator);
        int size = edges.size() - 1;
        while (!minHeap.isEmpty() && infos.size() < size) {
            Edge<V, E> edge = minHeap.remove();
            if (uf.isSame(edge.from, edge.to)) {
                continue;
            }
            infos.add(edge.info());
            uf.union(edge.from, edge.to);
        }
        return infos;
    }




    private static class Vertex<V, E> {

        private V value;

        private Set<Edge<V, E>> in;

        private Set<Edge<V, E>> out;

        public Vertex(V value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object obj) {
            return Objects.equals(value, ((Vertex<V, E>) obj).value);
        }

        @Override
        public int hashCode() {
            return value == null ? 0 : value.hashCode();
        }

        @Override
        public String toString() {
            return value == null ? "null" : value.toString();
        }
    }

    private static class Edge<V, E> {

        private E weight;

        private Vertex<V, E> from;

        private Vertex<V, E> to;

        public Edge(Vertex<V, E> from, Vertex<V, E> to) {
            this.from = from;
            this.to = to;
        }

        EdgeInfo<V, E> info() {
            return new EdgeInfo<>(from.value, to.value, weight);
        }

        @Override
        public boolean equals(Object obj) {
            Edge<V, E> edge = (Edge<V, E>) obj;
            return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            return from.hashCode() * 31 + to.hashCode();
        }

        @Override
        public String toString() {
            return "Edge [from=" + from + ", to=" + to + ", weight=" + weight + "]";
        }
    }


}
